package com.yww.datastructure.hashtable;

/**
 * @author yww
 * @description 哈希表
 * @since 2024/2/20 9:32
 */
public class HashTable<K, V> {
    Entry<K, V>[] table = (Entry<K, V>[]) new Entry[16]; // 哈希数组
    int size; // 元素个数
    final float loadFactor = 0.75f; // 扩容因子
    int threshold = (int) (loadFactor * table.length); // 扩容阈值


    public int hash(K key) {
        int hash = key.hashCode();
        return hash ^ (hash >>> 16);
    }

    public V get(K k) {
        return get(hash(k), k);
    }

    public void put(K key, V val) {
        put(hash(key), key, val);
    }

    public V remove(K key) {
        return remove(hash(key), key);
    }


    // 根据hash码、key获取值
    public V get(int hash, K k) {
        int idx = hash & (table.length - 1); // 计算索引
        Entry<K, V> p = table[idx];
        while (p != null) {
            if (k.equals(p.key)) {
                return p.val;
            }
            p = p.next;
        }
        return null;
    }

    public void put(int hash, K k, V val) {
        int idx = hash & (table.length - 1); // 计算索引
        if (table[idx] == null) { // 1. idx 处有空位, 直接新增
            table[idx] = new Entry<>(hash, k, val);
        } else {
            Entry<K, V> p = table[idx];
            while (true) { // 2. idx 处无空位, 沿链表查找 有重复key更新，否则新增
                if (p.key.equals(k)) { // 存在，更新
                    p.val = val;
                    return;
                }
                if (p.next == null) {
                    break;
                }
                p = p.next;
            }
            p.next = new Entry<>(hash, k, val); // 插入

        }
        size++;
        if (size > threshold) {
            resize();
        }
    }

    public V remove(int hash, K k) {
        int idx = hash & (table.length - 1);

        if (table[idx] == null) {
            return null;
        }
        Entry<K, V> p = table[idx];
        Entry<K, V> pre = null;
        while (p != null) {
            if (p.key.equals(k)) {
                if (pre == null) {
                    table[idx] = p.next;
                } else {
                    pre.next = p.next;
                }
                size--;
                return p.val;
            }
            pre = p;
            p = p.next;
        }
        return null;
    }

    private void resize() {
        Entry<K, V>[] newTable = (Entry<K, V>[]) new Entry[table.length << 1];
        for (int i = 0; i < table.length; i++) {
            Entry<K, V> p = table[i];
            if (p != null) {
                Entry<K, V> a = null;
                Entry<K, V> aHead = null;
                Entry<K, V> b = null;
                Entry<K, V> bHead = null;
                while (p != null) {
                    if ((p.hash & table.length) == 0) {
                        if (a != null) {
                            a.next = p;
                        } else {
                            aHead = p;
                        }
                        a = p;

                    } else {
                        if (b != null) {
                            b.next = p;
                        } else {
                            bHead = p;
                        }
                        b = p;

                    }
                    p = p.next;
                }
                if (a != null) {
                    a.next = null;
                    newTable[i] = aHead;
                }
                if (b != null) {
                    b.next = null;
                    newTable[i + table.length] = bHead;
                }
            }
        }
        table = newTable;
        threshold = (int) (loadFactor * table.length); // 扩容阈值

    }

    // 节点类
    static class Entry<K, V> {
        final int hash; // hash码
        K key; // 键
        V val; // 值
        Entry<K, V> next;

        public Entry(int hash, K key, V val) {
            this.hash = hash;
            this.key = key;
            this.val = val;
        }
    }
}
